/**
 * A permutation is an ordered arrangement of objects. For example, 3124 is one
 * possible permutation of the digits 1, 2, 3 and 4. If all of the permutations 
 * are listed numerically or alphabetically, we call it lexicographic order. 
 * The lexicographic permutations of 0, 1 and 2 are:
 *
 *   012   021   102   120   201   210
 *
 * What is the millionth lexicographic permutation of the digits 
 * 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
 *
 * ANSWER: 2783915460
 */

#include <iostream>
#include <utility>

template <typename Iterator>
bool nth_permutation(Iterator first, Iterator last, int n)
{
	const int max_fact = 12;
	static const int fact[max_fact+1] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 
		362880, 3628800, 39916800, 479001600 };
	if (n >= fact[max_fact])
		return false;

	int len = (int)(last - first);
	if (len > max_fact)
	{
		first += (max_fact - len);
		len = max_fact;
	}

	for (int k = len; k >= 1; k--)
	{
		int i = n / fact[k-1];
		for (int j = i; j > 0; j--)
		{
			std::swap(first[j], first[j-1]);
		}
		n %= fact[k-1];
		++first;
	}

	return true;
}

void solve_problem_24()
{
	char digits[] = "0123456789";
	
	nth_permutation(digits+0, digits+sizeof(digits)-1, 999999);
	std::cout << digits << std::endl;
}
